可以看出,选出区间的端点大小必须相同,不然可以将一端分在其他区间里,答案不会更劣。
令 表示前 个贝壳能得到的最大柠檬数, 表示第 个贝壳是第几个这种颜色的贝壳。
那么有转移:
假设两个决策 , 且 优于
因为最大值在队尾取到,所以用单调栈维护。
#include <cstdio>
#include <vector>
using namespace std;
#define LL long long
#define Lint long long
#define Top Stk[ s[ i ] ][ Stk[ s[ i ] ].size() - 1 ]
#define STop Stk[ s[ i ] ][ Stk[ s[ i ] ].size() - 2 ]
const int MAXN = 100000 , MAXC = 10000;
int n , s[ MAXN + 5 ] , pos[ MAXN + 5 ] , last[ MAXC + 5 ];
vector< int > Stk[ MAXC + 5 ];
LL dp[ MAXN + 5 ];
LL fx( int k , int i ) { return 1ll * s[ k ] * pos[ i ]; }
LL fy( int k , int i ) { return dp[ i - 1 ] + 1ll * s[ k ] * pos[ i ] * pos[ i ] - 2ll * s[ k ] * pos[ i ]; }
LL deltax( int k , int i , int j ) { return fx( k , i ) - fx( k , j ); }
LL deltay( int k , int i , int j ) { return fy( k , i ) - fy( k , j ); }
int main( ) {
scanf("%d",&n);
for( int i = 1 ; i <= n ; i ++ ) {
scanf("%d",&s[ i ]);
pos[ i ] = pos[ last[ s[ i ] ] ] + 1;
last[ s[ i ] ] = i;
}
for( int i = 1 ; i <= n ; i ++ ) {
for( ; Stk[ s[ i ] ].size() >= 2 && (Lint)deltay( i , STop , Top ) * deltax( i , Top , i ) <= (Lint)deltay( i , Top , i ) * deltax( i , STop , Top ) ; Stk[ s[ i ] ].pop_back() );
Stk[ s[ i ] ].push_back( i );
for( ; Stk[ s[ i ] ].size() >= 2 && (Lint)deltay( i , STop , Top ) >= (Lint)2 * pos[ i ] * deltax( i , STop , Top ) ; Stk[ s[ i ] ].pop_back() );
dp[ i ] = dp[ Top - 1 ] + 1ll * s[ i ] * ( pos[ i ] - pos[ Top ] + 1 ) * ( pos[ i ] - pos[ Top ] + 1 );
}
printf("%lld\n", dp[ n ] );
return 0;
}